package com.googlecode.carlosmonterocanabal.mojosprites.sprites;

import java.awt.Point;
import java.awt.Rectangle;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class ArevaloRectanglePacker extends RectanglePacker {

    private static class AnchorRankComparer implements Comparator<Point> {

        public static AnchorRankComparer Default = new AnchorRankComparer();

        public int compare(Point left, Point right) {
            return (left.x + left.y) - (right.x + right.y);
        }

    }

    private int actualPackingAreaHeight = 1;

    private int actualPackingAreaWidth = 1;

    private List<Point> anchors = new ArrayList<Point>(Arrays.asList(new Point(0, 0)));

    private List<Rectangle> packedRectangles = new ArrayList<Rectangle>();

    public ArevaloRectanglePacker(int packingAreaWidth, int packingAreaHeight) {
        super(packingAreaWidth, packingAreaHeight);
    }

    public Point tryPack(int rectangleWidth, int rectangleHeight) {

        int anchorIndex = SelectAnchorRecursive(rectangleWidth, rectangleHeight, actualPackingAreaWidth,
                actualPackingAreaHeight);

        // No anchor could be found at which the rectangle did fit in
        if (anchorIndex == -1) {
            // placement = new Point();
            return null;
        }

        Point placement = anchors.get(anchorIndex);

        // Move the rectangle either to the left or to the top until it collides with
        // a neightbouring rectangle. This is done to combat the effect of lining up
        // rectangles with gaps to the left or top of them because the anchor that
        // would allow placement there has been blocked by another rectangle
        optimizePlacement(placement, rectangleWidth, rectangleHeight);

        // Remove the used anchor and add new anchors at the upper right and lower left
        // positions of the new rectangle
        // The anchor is only removed if the placement optimization didn't
        // move the rectangle so far that the anchor isn't blocked anymore
        boolean blocksAnchor = ((placement.x + rectangleWidth) > anchors.get(anchorIndex).x)
                && ((placement.y + rectangleHeight) > anchors.get(anchorIndex).y);

        if (blocksAnchor)
            anchors.remove(anchorIndex);

        // Add new anchors at the upper right and lower left coordinates of the rectangle
        InsertAnchor(new Point(placement.x + rectangleWidth, placement.y));
        InsertAnchor(new Point(placement.x, placement.y + rectangleHeight));

        // Finally, we can add the rectangle to our packed rectangles list
        packedRectangles.add(new Rectangle(placement.x, placement.y, rectangleWidth, rectangleHeight));

        return placement;
    }

    private void optimizePlacement(Point placement, int rectangleWidth, int rectangleHeight) {
        Rectangle rectangle = new Rectangle(placement.x, placement.y, rectangleWidth, rectangleHeight);

        // Try to move the rectangle to the left as far as possible
        int leftMost = placement.x;
        while (isFree(rectangle, PackingAreaWidth, PackingAreaHeight)) {
            leftMost = rectangle.x;
            --rectangle.x;
        }

        // Reset rectangle to original position
        rectangle.x = placement.x;

        // Try to move the rectangle upwards as far as possible
        int topMost = placement.y;
        while (isFree(rectangle, PackingAreaWidth, PackingAreaHeight)) {
            topMost = rectangle.y;
            --rectangle.y;
        }

        // Use the dimension in which the rectangle could be moved farther
        if ((placement.x - leftMost) > (placement.y - topMost))
            placement.x = leftMost;
        else
            placement.y = topMost;
    }

    private int SelectAnchorRecursive(int rectangleWidth, int rectangleHeight, int testedPackingAreaWidth,
            int testedPackingAreaHeight) {
        // Try to locate an anchor point where the rectangle fits in
        int freeAnchorIndex = FindFirstFreeAnchor(rectangleWidth, rectangleHeight, testedPackingAreaWidth,
                testedPackingAreaHeight);

        // If a the rectangle fits without resizing packing area (any further in case
        // of a recursive call), take over the new packing area size and return the
        // anchor at which the rectangle can be placed.
        if (freeAnchorIndex != -1) {
            actualPackingAreaWidth = testedPackingAreaWidth;
            actualPackingAreaHeight = testedPackingAreaHeight;

            return freeAnchorIndex;
        }

        //
        // If we reach this point, the rectangle did not fit in the current packing
        // area and our only choice is to try and enlarge the packing area.
        //

        // For readability, determine whether the packing area can be enlarged
        // any further in its width and in its height
        boolean canEnlargeWidth = (testedPackingAreaWidth < PackingAreaWidth);
        boolean canEnlargeHeight = (testedPackingAreaHeight < PackingAreaHeight);
        boolean shouldEnlargeHeight = (!canEnlargeWidth) || (testedPackingAreaHeight < testedPackingAreaWidth);

        // Try to enlarge the smaller of the two dimensions first (unless the smaller
        // dimension is already at its maximum size). 'shouldEnlargeHeight' is true
        // when the height was the smaller dimension or when the width is maxed out.
        if (canEnlargeHeight && shouldEnlargeHeight) {
            // Try to double the height of the packing area
            return SelectAnchorRecursive(rectangleWidth, rectangleHeight, testedPackingAreaWidth,
                    Math.min(testedPackingAreaHeight * 2, PackingAreaHeight));
        }
        if (canEnlargeWidth) {
            // Try to double the width of the packing area
            return SelectAnchorRecursive(rectangleWidth, rectangleHeight,
                    Math.min(testedPackingAreaWidth * 2, PackingAreaWidth), testedPackingAreaHeight);
        }

        // Both dimensions are at their maximum sizes and the rectangle still
        // didn't fit. We give up!
        return -1;
    }

    private int FindFirstFreeAnchor(int rectangleWidth, int rectangleHeight, int testedPackingAreaWidth,
            int testedPackingAreaHeight) {
        Rectangle potentialLocation = new Rectangle(0, 0, rectangleWidth, rectangleHeight);

        // Walk over all anchors (which are ordered by their distance to the
        // upper left corner of the packing area) until one is discovered that
        // can house the new rectangle.
        for (int index = 0; index < anchors.size(); ++index) {
            potentialLocation.x = anchors.get(index).x;
            potentialLocation.y = anchors.get(index).y;

            // See if the rectangle would fit in at this anchor point
            if (isFree(potentialLocation, testedPackingAreaWidth, testedPackingAreaHeight))
                return index;
        }

        // No anchor points were found where the rectangle would fit in
        return -1;
    }

    private boolean isFree(Rectangle rectangle, int testedPackingAreaWidth, int testedPackingAreaHeight) {
        // If the rectangle is partially or completely outside of the packing
        // area, it can't be placed at its current location
        boolean leavesPackingArea = (rectangle.x < 0) || (rectangle.y < 0)
                || (rectangle.height + rectangle.y > testedPackingAreaHeight)
                || (rectangle.width + rectangle.x > testedPackingAreaWidth);

        if (leavesPackingArea)
            return false;

        // Brute-force search whether the rectangle touches any of the other
        // rectangles already in the packing area
        for (int index = 0; index < packedRectangles.size(); ++index) {
            if (packedRectangles.get(index).intersects(rectangle))
                return false;
        }

        // Success! The rectangle is inside the packing area and doesn't overlap
        // with any other rectangles that have already been packed.
        return true;
    }

    private void InsertAnchor(Point anchor) {
        // Find out where to insert the new anchor based on its rank (which is
        // calculated based on the anchor's distance to the top left corner of
        // the packing area).
        //
        // "If the List does not contain the specified value, the method returns
        // a negative integer. You can apply the bitwise complement operation (~) to
        // this negative integer to get the index of the first element that is
        // larger than the search value."
        int insertIndex = Collections.binarySearch(anchors, anchor, AnchorRankComparer.Default);
        if (insertIndex < 0)
            insertIndex = ~insertIndex;

        // Insert the anchor at the index matching its rank
        anchors.add(insertIndex, anchor);
    }
}
